package com.practice.recursive;

/**
 * Find kth permute string of input.
 */
public class PermuteK {
	private int[] P;
	
	public String permute(String input, int k) {
		calculatePermuteNumber(input.length());
		return find(input, k);
	}

	private void calculatePermuteNumber(int N) {
		P = new int[N];
		P[0] = 1;
		for (int i=1; i<N; i++) {
			P[i] = P[i-1]*i;
		}
	}
	
	private String find(String input, int k) {
		int N = input.length();
		if (N == 1) return input;
		int i = k/P[N-1];
		int j = k%P[N-1];
		return input.charAt(i) + find(input.substring(0, i) + input.substring(i+1), j);
	}
	
	public int getRank(String input) {
		calculatePermuteNumber(input.length());
		int rank = 0;
		char[] c = input.toCharArray();
		for (int i=0; i<c.length; i++) {
			int k = 0;
			for (int j=i+1; j<c.length; j++) {
				if (c[i] > c[j]) k++;
			}
			rank += k * P[c.length - i - 1];
		}
		return rank;
	}
}
